package org.hmh.offer;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created this one by HMH on 2018/1/20.
 */
public class t242 {
    static public class Solution {
        public ArrayList<String> Permutation(String str) {
            ArrayList<String> res = new ArrayList<String>();
            if (str ==null || str.length() == 0) return res;
            int n = str.length();
            helper(res, 0, str.toCharArray());
            Collections.sort(res);
            return res;

        }

        public void helper(ArrayList<String> res, int index, char[] s) {
            if (index == s.length - 1) res.add(new String(s));
            for (int i = index; i < s.length; i++) {
                if (i == index || s[index] != s[i]) {
                    swap(s, index, i);
                    helper(res, index + 1, s);
                    swap(s, index, i);
                }
            }

        }

        public void swap(char[] t, int i, int j) {
            char c = t[i];
            t[i] = t[j];
            t[j] = c;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        System.out.println(solution.Permutation("abcc"));
    }
}
